class Solution {
public:
    int tmp = 1000000007;
    vector<int>f;
    int waysToStep(int n) {
        f = vector<int>(n + 1);
        return dfs(n);
    }
    int dfs(int a)
    {
        if (a == 1 || a == 2)return a;
        if (a == 3)return 4;
        if (f[a] != 0)return f[a];
        f[a] = ((dfs(a - 1) % tmp + dfs(a - 2) % tmp) % tmp + dfs(a - 3) % tmp) % tmp;
        return f[a];
    }
};
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int a[3]={0};//5,10,20
        for(auto e:bills)
        {
            if(e==5)a[0]++;
            else if(e==10)
            {
                if(a[0]==0)return false;
                else a[0]--;
                a[1]++;
            }
            else
            {
                if(a[1]>0)
                {
                    if(a[0]==0)return false;
                    else
                    {
                        a[0]--;
                        a[1]--;
                    }
                }
                else
                {
                    if(a[0]<3)return false;
                    else a[0]-=3;
                }
            }
        }
        return true;
    }
};
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return 1;
        int i=1;
        while(i<n&&nums[i-1]==nums[i])i++;
        if(i==n)return 1;
        int sign=0;
        if(nums[i]>nums[i-1])sign=1;
        else sign=-1;
        int ret=2;
        for(i=i+1;i<n;i++)
        {
            if(sign==1&&nums[i]<nums[i-1])ret++,sign=-1;
            else if(sign==-1&&nums[i]>nums[i-1])ret++,sign=1;
        }
        return ret;
    }
}；
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
       vector<int>f(n+1);
       for(int i=2;i<=n;i++)
       {
            f[i]=min(cost[i-2]+f[i-2],cost[i-1]+f[i-1]);
       }
       return f[n];
    }
};
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return 1;
        int i=1;
        while(i<n&&nums[i-1]==nums[i])i++;
        if(i==n)return 1;
        vector<int>f(n,1);//最少为1，只有自己时
        auto g=f;
        if(nums[i]>nums[i-1])f[i]=2;
        else g[i]=2;
        int ret=2;//最少为2
        for(int j=i+1;j<n;j++)
        {
            for(int k=j-1;k>=i-1;k--)
            {
                if(nums[j]>nums[k])f[j]=max(f[j],g[k]+1);//看升序能跟在哪个元素的后面
                if(nums[j]<nums[k])g[j]=max(g[j],f[k]+1);
            }
            ret=max(ret,f[j]);
            ret=max(ret,g[j]);
        }
        return ret;
    }
};
class Solution {
public:
    int numDecodings(string s) {
        if(s[0]=='0')return 0;
        int n=s.size();
        vector<int>f(n+1);//垫出一位，因为后面要访问前面两个元素
        f[0]=1;//根据f[2]实际情况填写的，f[0]只能影响到f[2]
        f[1]=1;
        for(int i=2;i<=n;i++)//总归就是自己成，自己和前面一个成
        {
            if(s[i-1]=='0')
            {
                if(s[i-2]!='1'&&s[i-2]!='2')return 0;
                else f[i]=f[i-2];
            }
            else
            {
                f[i]+=f[i-1];
                if(stoi(s.substr(i-2,2))>10&&stoi(s.substr(i-2,2))<=26)f[i]+=f[i-2];
            }
        }
        return f[n];
    }
};
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
        if(ob[0][0]==1)return 0;
        int m=ob.size();
        int n=ob[0].size();
        vector<vector<int>>f(m,vector<int>(n));
        for(int i=0;i<m;i++)
        {
            if(ob[i][0]==0)f[i][0]=1;
            else break;
        }
        for(int i=1;i<n;i++)
        {
            if(ob[0][i]==0)f[0][i]=1;
            else break;
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(ob[i][j]==1)continue;
                f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
return f[m-1][n-1];
    }
};
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m=frame.size();
        int n=frame[0].size();
        vector<vector<int>>f(m+1,vector<int>(n+1));//为了方便，提前开出上一行左一列
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                f[i][j]=max(f[i-1][j],f[i][j-1])+frame[i-1][j-1];
            }
        }
        return f[m][n];
    }
};
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int tmp=0x3f3f3f3f;
        int n=matrix.size();
        vector<vector<int>>f(n,vector<int>(n+2,tmp));//关键是左边补一列，右边补一列，为了后边方便
        for(int i=1;i<=n;i++)f[0][i]=matrix[0][i-1];//初始化
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i-1][j+1])+matrix[i][j-1];
            }
        }
        int ret=tmp;
        for(int i=1;i<=n;i++)ret=min(ret,f[n-1][i]);
        return ret;
    }
};
class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int m=costs.size();
        vector<vector<int>>f=costs;
        for(int i=1;i<m;i++)
        {
            f[i][0]=min(f[i-1][1],f[i-1][2])+costs[i][0];
            f[i][1]=min(f[i-1][0],f[i-1][2])+costs[i][1];
            f[i][2]=min(f[i-1][0],f[i-1][1])+costs[i][2];
        }
        int ret=f[m-1][0];
        ret=min(ret,f[m-1][1]);
        ret=min(ret,f[m-1][2]);
        return ret;
    }
};
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        map<int,int>hash;
        for(auto e:nums)hash[e]+=e;
        vector<pair<int,int>>f(hash.begin(),hash.end());//换成数组为了方便用0-n的下标访问
        int n=f.size();
        vector<int>dp(n+1);
        dp[1]=f[0].second;
        for(int i=2;i<=n;i++)
        {
            if(f[i-1-1].first+1==f[i-1].first)dp[i]=max(dp[i-1],dp[i-2]+f[i-1].second);//连续两个数
            else dp[i]=dp[i-1]+f[i-1].second;//不连续
        }
        return dp[n];
    }
};
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& d) {
        int m=d.size();
        int n=d[0].size();
        vector<vector<int>>f(m+1,vector<int>(n+1,INT_MAX));
        f[m][n-1]=1;//从后往前，并且走完最后一个格子血量要为1
        for(int i=m-1;i>=0;i--)
        {
            for(int j=n-1;j>=0;j--)
            {
                f[i][j]=min(f[i+1][j],f[i][j+1])-d[i][j];
                if(f[i][j]<=0)f[i][j]=1;
            }
        }
        return f[0][0];
    }
};
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        if(n==1)return 0;
        vector<vector<int>>f(2,vector<int>(n));
        f[0][0]=-prices[0];
        for(int i=1;i<n;i++)
        {
            f[0][i]=max(f[0][i-1],f[1][i-1]-prices[i]);//这一排必须是买入状态
            f[1][i]=max(f[1][i-1],f[0][i-1]+prices[i]-fee);//这一排是手中无股票的状态
        }
        return f[1][n-1];
    }
};
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1)return 0;
        vector<vector<int>>f(3,vector<int>(n));
        f[0][0]=-prices[0];
        for(int i=1;i<n;i++)
        {
            f[0][i]=max(f[0][i-1],f[2][i-1]-prices[i]);//这一排必须是买入状态
            f[1][i]=f[0][i-1]+prices[i];//这一排必须是卖出状态
            f[2][i]=max(f[2][i-1],f[1][i-1]);//这一排是手上没有股票的状态，可以是自由交易，可以是冷冻期
        }
        return max(f[1][n-1],f[2][n-1]);
    }
};
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1)return 0;
        vector<vector<int>>f(5,vector<int>(n));
        f[0][0]=f[1][0]=-prices[0];
        for(int i=1;i<n;i++)
        {
            f[0][i]=max(f[0][i-1],-prices[i]);
            f[1][i]=max(f[1][i-1],f[3][i-1]-prices[i]);
            f[3][i]=max(f[3][i-1],f[0][i-1]+prices[i]);
            f[4][i]=max(f[4][i-1],f[1][i-1]+prices[i]);
        }
        return max(max(f[2][n-1],f[3][n-1]),f[4][n-1]);
    }
};
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1)return 0;
        vector<int>f;
        int begin=prices[0];
        int tmp=0;
        for(int i=1;i<n;i++)
        {
            if(prices[i-1]>prices[i])
            {
                if(tmp==1&&prices[i-1]-begin>f[f.size()-1])f.pop_back();
                f.push_back(prices[i-1]-begin);
                tmp=1;
                if(begin>prices[i]) 
                {
                    begin=prices[i];
                    tmp=0;
                }

                
            }
        }
        if(tmp==1&&prices[n-1]-begin>f[f.size()-1])f.pop_back();
        if(prices[n-1]>begin)f.push_back(prices[n-1]-begin);
        sort(f.begin(),f.end(),greater<int>());
        if(f.size()==0)return 0;
        if(f.size()==1)return f[0];
        return f[0]+f[1];


    }
};
#include <iostream>
#include<vector>
#include <cmath>
using namespace std;
void jump(int i,vector<int>&f,int m)
{
    int tmp=f[i];
    for(int j=2;j<=(int)sqrt(i);j++)
    {
        if(i%j==0)
        {
            if(i+j<=m)
            {
                if(f[i+j]==-1)f[i+j]=tmp+1;
                else f[i+j]=min(f[i+j],tmp+1);
            }
            if(i+i/j<=m&&j*j!=i)
            {
                if(f[i+i/j]==-1)f[i+i/j]=tmp+1;
                else f[i+i/j]=min(f[i+i/j],tmp+1);
            }
        }
    }
}
int main() {
    int n,m;
    cin>>n>>m;
    vector<int>f(m+1,-1);
    f[n]=0;
    for(int i=n;i<m;i++)
    {
        if(f[i]!=-1)
            jump(i,f,m);
    }
    cout<<f[m]<<endl;
    return 0;
}
class Solution {
public:
TreeNode*ret;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p,q);
        return ret;
    }
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if(root==nullptr)return false;
        bool b1=dfs(root->left,p,q);
        bool b2=dfs(root->right,p,q);
        if(b1&&b2||b1&&(root==p||root==q)||b2&&(root==p||root==q))
        {
            ret=root; 
            return false;
        }
        else if(b1||b2||root==p||root==q)return true;
        else return false;
    }
};
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* root) {
        if(root==nullptr)return nullptr;
		TreeNode*cur=root;
		while(cur->left!=nullptr)cur=cur->left;
		makeit(root);

		return cur;
    }
	TreeNode* makeit(TreeNode*n)
	{
		if(n==nullptr)return nullptr;
		TreeNode* t1=makeit(n->left);
		TreeNode* t2=makeit(n->right);
		if(t1==nullptr&&t2==nullptr)return n;
		if(t1&&t2==nullptr)
		{
			t1->right=n;
			n->left=t1;
			return n;
		}
		if(t1==nullptr&&t2)
		{
			n->right=t2;
			t2->left=n;
			return t2;
		}
		if(t1&&t2)
		{
			t1->right=n;
			n->left=t1;
			n->right=t2;
			t2->left=n;
			return t2;
		}
		return nullptr;
	}
};
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n=arr.size();
        if(n==1||n==2&&arr[0]==arr[1])return 1;
        if(n==2&&arr[0]!=arr[1])return 2;
        int ret=1;
        int tmp=1;
        int sign=0;
        for(int i=1;i<n;i++)
        {
            if(arr[i]>arr[i-1]&&sign!=1||arr[i]<arr[i-1]&&sign!=-1)
            {
                tmp++;
                if(arr[i]>arr[i-1])sign=1;
                else sign=-1;
            }
            else if(arr[i]==arr[i-1])
            {
                ret=max(ret,tmp);
                tmp=1;
                sign=0;
            }
            else
            {
                if(arr[i]>arr[i-1])
                {
                    ret=max(ret,tmp);
                    tmp=2;
                    sign=1;
                }
                else
                {
                    ret=max(ret,tmp);
                    tmp=2;
                    sign=-1;
                }
            }
        }
        ret=max(ret,tmp);
        return ret;
    }
};
class Solution {
public:
unordered_set<string> hash;
    bool wordBreak(string s, vector<string>& wordDict) {
        for(auto&e:wordDict)hash.insert(e);
        return analyse(s);
    }
    bool analyse(string s)
    {
        for(int i=1;i<=s.size();i++)
        {
            if(hash.count(s.substr(0,i)))
            {
                if(i==s.size())return true;
                bool ret=analyse(s.substr(i));
                if(ret)return true;
            }
        }
        return false;
    }
};
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string>hash;
        for(auto&e:wordDict)hash.insert(e);
        int n=s.size();
        vector<bool>f(n+1);
        s=' '+s;
        f[0]=true;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j>0;j--)
            {
                if(f[j-1]&&hash.count(s.substr(j,i-j+1)))
                {
                    f[i]=true;
                    break;
                }
            }
        }
        return f[n];
    }
};
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int>f;
        f.push_back(nums[0]);
        for(int i=1;i<n;i++)
        {
            if(nums[i]>f.back())f.push_back(nums[i]);
            else if(nums[i]<f.back())
            {
                for(int j=0;j<f.size();j++)
                {
                    if(f[j]>=nums[i])
                    {
                        f[j]=nums[i];
                        break;
                    }
                }
            }
        }
        return f.size();
    }
};
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int>len(n,1);
        vector<int>cnt(n,1);
        int tmplen=1;
        int tmpcnt=1;
        for(int i=1;i<n;i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(nums[j]<nums[i])
                {
                    if(len[j]+1>len[i])
                    {
                        len[i]=len[j]+1;
                        cnt[i]=cnt[j];
                    }
                    else if(len[j]+1==len[i])cnt[i]+=cnt[j];
                }
            }
                if(len[i]>tmplen)
                {
                    tmplen=len[i];
                    tmpcnt=cnt[i];
                }
                else if(len[i]==tmplen)tmpcnt+=cnt[i];
        }
        return tmpcnt;
    }
};
class Solution {
public:
    bool checkPartitioning(string s) {
        int n=s.size();
        vector<vector<bool>>f(n,vector<bool>(n));
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j||i+1==j)f[i][j]=true;
                    else
                    {
                        if(f[i+1][j-1])f[i][j]=true;
                    }
                }
            }
        }
        for(int i=0;i<=n-3;i++)
        {
            if(f[0][i]==true)
            {
                for(int j=i+1;j<=n-2;j++)
                {
                    if(f[i+1][j]==true)
                    {
                        if(f[j+1][n-1]==true)return true;
                    }
                }
            }
        }
        return false;
    }
};
class Solution {
public:
    int n;
    vector<vector<bool>>f;
    int ret=INT_MAX;

    int minCut(string s) {
        n=s.size();
        if(n==1)return 0;
        f=vector<vector<bool>>(n,vector<bool>(n));
        
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j||i+1==j||f[i+1][j-1])f[i][j]=true;                }
            }
        }
        for(int i=0;i<n;i++)
        {
            int tmp=0;
            if(f[0][i])
            {
                if(i==n-1)return 0;
                else tmp=1;
                dfs(i+1,tmp);
            }
        }
        return ret;
    }
    void dfs(int pos,int tmp)
    {
        if(pos==n)
        {
            ret=min(ret,tmp-1);
            return;
        }
        for(int i=pos;i<n;i++)
        {
            if(f[pos][i])
            {
                dfs(i+1,tmp+1);
            }
        }
    }
};
class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        if(n==1)return 0;
        vector<vector<bool>>f(n,vector<bool>(n));
        
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j||i+1==j||f[i+1][j-1])f[i][j]=true;    
                }            
            }
        }
        vector<int>g(n+1,INT_MAX);
        g[0]=-1;
        g[1]=0;
        for(int i=2;i<=n;i++)
        {
            for(int j=i;j>=1;j--)
            {
                if(f[j-1][i-1])
                {
                    g[i]=min(g[i],g[j-1]+1);
                }
            }
        }
        return g[n];
    }
};
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n1=nums1.size();
        int n2=nums2.size();
        vector<vector<int>>f(n1+1,vector<int>(n2+1,0));
        for(int i=1;i<=n1;i++)
        {
            for(int j=1;j<=n2;j++)
            {
                if(nums1[i-1]==nums2[j-1])
                    f[i][j]=f[i-1][j-1]+1;
                else
                    f[i][j]=max(f[i-1][j],f[i][j-1]);
            }
        }
        return f[n1][n2];
    }
};
class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        if(n==1)return 0;
        vector<vector<bool>>f(n,vector<bool>(n));
        
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j||i+1==j||f[i+1][j-1])f[i][j]=true;    
                }            
            }
        }
        vector<int>g(n+1,INT_MAX);
        g[0]=-1;
        g[1]=0;
        for(int i=2;i<=n;i++)
        {
            for(int j=i;j>=1;j--)
            {
                if(f[j-1][i-1])
                {
                    g[i]=min(g[i],g[j-1]+1);
                }
            }
        }
        return g[n];
    }
};
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1=s1.size();
        int n2=s2.size();
        if(n1+n2!=s3.size())return false;
        s1=' '+s1;
        s2=' '+s2;
        s3=' '+s3;
        vector<vector<bool>>f(n1+1,vector<bool>(n2+1));
        f[0][0]=true;
        for(int i=1;i<=n1;i++)
        {
            if(s1[i]==s3[i])f[i][0]=true;
            else break;
        }
        for(int i=1;i<=n2;i++)
        {
            if(s2[i]==s3[i])f[0][i]=true;
            else break;
        }
        for(int i=1;i<=n1;i++)
        {
            for(int j=1;j<=n2;j++)
            {
                if(s1[i]==s3[i+j]&&f[i-1][j]||s2[j]==s3[i+j]&&f[i][j-1])f[i][j]=true;
            }
        }
        return f[n1][n2];
    }
};
#include <iostream>
#include<unordered_map>
#include<vector>
using namespace std;

int main() {
    int n=0,V=0;
    cin>>n>>V;
    vector<vector<int>>obj(n+1,vector<int>(2));
    for(int i=1;i<=n;i++)
    {
        cin>>obj[i][0]>>obj[i][1];
    }
    vector<int>f(V+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=obj[i][0];j--)
        {
            f[j]=max(f[j],f[j-obj[i][0]]+obj[i][1]);
        }
    }
    cout<<f[V]<<endl;
    vector<int>g(V+1,-1);
    g[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=obj[i][0];j--)
        {
            if(g[j-obj[i][0]]!=-1)g[j]=max(g[j],g[j-obj[i][0]]+obj[i][1]);
        }
    }
    cout<<(g[V]==-1?0:g[V])<<endl;
    
}
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int sum=0;
        for(auto e:s1)sum+=e;
        for(auto e:s2)sum+=e;

        int n1=s1.size();
        int n2=s2.size();
        vector<vector<int>>f(n1+1,vector<int>(n2+1));//i,j为结尾，最长公共子序列的ASCII和
        for(int i=1;i<=n1;i++)
        {
            for(int j=1;j<=n2;j++)
            {
                if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1]+s1[i-1];
                else
                {
                    f[i][j]=max(f[i-1][j],f[i][j-1]);
                }
            }
        }
        return sum-2*f[n1][n2];
    }
};
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto e:nums)sum+=e;
        if(sum%2==1)return false;
        sum/=2;
        vector<bool>f(sum+1);
        f[0]=true;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=sum;j-nums[i]>=0;j--)
            {
                if(f[j-nums[i]]==true)f[j]=true;
            }
        }
        return f[sum];
    }
};
class Solution {
public:
int tar;
int ret;
    int findTargetSumWays(vector<int>& nums, int target) {
        tar=target;
        dfs(nums,0,0);
        return ret;
    }
    void dfs(vector<int>& nums,int pos,int sum)
    {
        if(pos==nums.size()&&sum==tar)
        {
            ret++;
            return;
        }
        if(pos==nums.size())return;
        dfs(nums,pos+1,sum+nums[pos]);
        dfs(nums,pos+1,sum-nums[pos]);
    }
};
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        int n=nums.size();
        for(auto e:nums)sum+=e;
        int x=target+sum;
        if(x%2==1)return 0;
        x/=2;
        vector<int>f(x+1);
        f[0]=1;
        for(int i=0;i<n;i++)
        {
            for(int j=x;j>=0;j--)
            {
                if(j-nums[i]>=0)
                {
                    f[j]+=f[j-nums[i]];
                }
            }
        }
        return f[x];
    }
};
